#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtrack(board);
    }
private:
    bool backtrack(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char num = '1'; num <= '9'; num++) {
                        if (isvaild(board,i,j,num)) {
                            board[i][j] = num;
                            if(backtrack(board)){return true;}
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    bool isvaild(vector<vector<char>>& board,int row,int col,char num) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == num)return false;
        }
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num)return false;
        }
        int startrow = (row / 3) * 3;
        int startcol = (col / 3) * 3;
        for (int i = startrow; i < startrow+3; i++) {
            for (int j = startcol; j < startcol+3; j++) {
                if (board[i][j] == num)return false;
            }
        }
        return true;
    }
};